1. Field of the Invention
This invention relates to the field of anti-aliased text. More particularly, the invention relates to the storage of anti-aliased text data information and the displaying/rendering of such anti-aliased text in real time.
2. Background Art
When words or text are displayed on a computer display, it is desirable that the edges of each letter be smooth and look realistic. Text that does not look smooth is sometimes referred to as "aliased" text. The current methods of solving the problems of aliased text are slow and use too much computer memory. A background of computer displays and the problems of antialiased text, along with a description of the disadvantages of prior art antialias schemes, is described below.
If you looked closely at a computer display, you would see that an image is made up of hundreds or thousands of tiny dots, where each dot is a different color. These dots are known as picture elements, or "pixels" for short. The color of each pixel is represented by a number value. To store an image in a computer memory, the number value of each pixel of the picture is stored. The number value represents the color and intensity of the pixel.
FIG. 1 is an enlarged portion of a display screen. Each square represents a pixel on a display device. The horizontal line is referred to as the x-axis and the vertical line is referred to as the y-axis. When a text character or symbol is drawn on a display device, the objective is to draw a series of small solid lines which make up that text character. FIG. 1 illustrates how a user would prefer to have a line (or part of a character) drawn on a display device. In this respect, line 102 can be viewed as a part of an ideal text character. An ideal line may not fill an entire pixel. For example, line 102 only uses part of pixel 104 and an even smaller portion of pixel 106. However, when displaying a line, the user cannot turn on a part of a pixel. The user may adjust the levels of intensity of that pixel, but the entire pixel must be illuminated.
When drawing a line or writing text (which contains many lines), the first step is to choose which initial pixel will be illuminated. Thus, in FIG. 1, the first (initial) pixel that would be chosen to be turned on would be that at location (1,1) or pixel 108. The next pixel is then chosen. In FIG. 1, the next pixel chosen to be illuminated is either pixel 104 or pixel 106. For purposes of example, assume that the computer selects pixel 104 (due to the fact that a higher percentage of pixel 104 contains the line than the percentage contained in pixel 106). The computer then must choose the next pixel, which will likely be pixel 110, then pixel 112. The resulting line is then illuminated and is illustrated in FIG. 2, with pixels 208, 204, 210, and 212 illuminated. The pixels of the text line are black, the pixels of the background are white. As demonstrated in FIG. 2, the line has "jaggy" or "jagged" edges, or the appearance of a staircase. Such an appearance is referred to as "aliasing". FIG. 2 demonstrates aliasing at the pixel level. FIG. 3 demonstrates the effect of aliasing at an increased or viewing level. The text message "Hello, World" of FIG. 3 is aliased. The individual letters of "Hello, World" have jagged edges and a staircase effect. Such aliasing can be more clearly seen in the magnified view of the letter "o" in FIG. 3.
Anti-aliasing is the process of smoothing the "jaggy" edges typically associated with text drawn on computer screens. To smooth the "jaggy" edges, various different levels of intensity are applied to the surrounding/boundary pixels. Such smoothing is performed by combining the color of the source (or the line/text) and the destination (background). Instead of filling all of the pixels with the same intensity level, all pixels that are overlapped by the line area are displayed with an intensity proportional to the area of overlap. Thus, if a pixel has about half its area inside of the line/text, the intensity of that pixel would be adjusted to one-half of its normal intensity. In the same manner, if a pixel has about one-third of its area inside of the line/text, the intensity of that pixel would be adjusted to one-third of its normal intensity. Similar adjustments, based on the percent of pixel area coverage, are applied to the other intensity values around the border.
FIG. 4 illustrates smoothing at the pixel level. Rather than leaving pixel 406 (or pixel 206 of FIG. 2) blank or non-illuminated, an anti-aliasing process would illuminate pixel 406 with an intermediate level of intensity. Since about one-eighth of pixel 406 is inside the line (see pixel 106 of FIG. 1), the intensity level of 406 would be adjusted to about one-eighth of 100%. The level of intensity is applied in the color of the text. In the example of FIG. 4, the source (text) color is black. As a result, one-eighth of 100% black is illuminated in pixel 406.
Similarly, instead of completely illuminating pixel 404 (or pixel 204 of FIG. 2), an intermediate shade is illuminated (about one-third of 100% due to the fact that about one-third of the pixel is inside the line). Referring to FIG. 1, it can be seen that the line 102 consumes a greater percentage of pixel 104 than of pixel 106. As a result, the intensity level of pixel 104 should be slightly higher/darker than that of pixel 106 (one-third verses one-eighth). Such a difference in intensity levels can be seen in FIG. 4. Pixel 404 has a slightly darker shade than that of pixel 406.
By illuminating the surrounding/boundary pixels at varying levels of intensity, the staircase effect diminishes. Moreover, when viewed from a distance, the staircase effect appears significantly diminished. Referring to FIG. 5, the process above has been applied to the aliased version of "Hello World" (text of FIG. 3). The message "Hello, World" of FIG. 5 now appears smooth at the curved and slanted boundaries. The magnified view of the letter "o" to the right reveals that some of the pixels at the boundary between the letter and the background have been shaded to a blend of the background and text colors. The process of coloring and drawing anti-aliased text with appropriate shading of the boundary pixels is referred to as rendering of anti-aliased text.
Various prior art anti-aliasing methods have developed. One prior art method is termed "pixel phasing". In pixel phasing, intensities of line edges are adjusted by "micropositioning" of the electron beam. Thus, the electron beam which illuminates a pixel is repositioned. The systems incorporating this technique are designed so that individual pixel positions can be shifted by a fraction of a pixel diameter. By allowing shifts of 1/4, 1/2, and 3/4 of a pixel diameter, a line can be displayed by plotting points closer to the true path of the line. Thus, the pixels (pixel beam) themselves are repositioned and illuminated. These systems also allow the size of individual pixels to be altered. However, such a prior art approach requires additional computer hardware which permits such repositioning of the pixels. Further, such a method will leave gaps in the areas where the pixel position has been shifted away from.
FIG. 6 shows an example of another prior art method. According to this method, the raw text is drawn at a larger size (typically four times the size) than the final size. For example, the text "Hello, World" is drawn in large size (e.g. four times larger) in FIG. 6 (602). In this manner, each pixel can be divided into four sub-pixels. Such a division permits one to estimate how much of a pixel is inside the line or text. For example, if three out of the four subpixels are inside of the line/text, then the intensity level will be adjusted to 75%. Similarly, if two out of the four subpixels are inside of the line/text, then the intensity level will be adjusted to 50%.
The image is then shrunk to create a mask 604, also called an "alpha channel mask." The mask contains all of the intensity levels to be utilized. As can be seen in the magnified view 606, the mask contains intermediate levels of intensity in the boundary/surrounding pixels. This mask is used to blend a representation of the text "Hello, World" into the background. In this prior art method, both the source image (text/line) 602 and the mask 604 are stored, using memory resources.
To render or draw the image onto the display device, each bit of the source image (the text "Hello, World", color and pattern information) is blended with the mask image (604) and applied to the destination (a computer display screen), a time consuming process and one which must be repeated many times if the text is moved or scrolled on the display. In other words, the mask retains the information regarding the various level of intensities and the original source image/text retains the information regarding what color or pattern the text is.
For example, assume that the message "Hello, World" is comprised of multiple colors, such that half of the "H" is blue and half is green. In the same respect, assume that the remaining letters change so that the phrase "Hello, World" is made up of all the colors of the rainbow. The mask would contain information on the "H" such that a pixel in the middle of the H is illuminated in 100% of the source color. The mask does not contain information regarding what that source color is.
The source image retains the color information. As a result, the source image would contain the color blue for that pixel, or a mix of green and blue for another part of the H. The mask would also contain information of a pixel towards the boundary of "H" such that the particular pixel only gets 50% of some source color (whatever it may be). The source image (the text "Hello, World" in all of the colors) provides the source color. In this manner, for each pixel, the source color is obtained from the source image and applied to the destination according to the percentages from the mask. Thus, when rendering the final anti-aliased image to the screen, the mask/intensity value is obtained . . . the color is obtained . . . and the pixel is displayed in the appropriate color with the appropriate intensity. In this respect, both the source image and the mask are utilized.
This prior art method of enlarging the text, shrinking the text to create a mask and rendering the image, is known as "super-sampling and reduction". In short, this method creates an alpha channel mask through which anti-aliased text is rendered. This method is slow in that it requires approximately one to two seconds to draw a full screen of the anti-aliased text. The method also requires large amounts of memory to store the image of the raw text (source image and color) and the alpha channel mask. In other words the prior art stores an uncompressed bitmap form of the text and the mask information, both of which are memory intensive.
Another prior art method, extracts vector information out of an outline font (TrueType and Postscript fonts) and calculates the value of every pixel as it is drawn. In other words, the outline information of a particular font, which is made up of a series of bezier curves (which make up each character), is read. Using this outline information, the amount/percentage of the pixel which needs to be drawn is calculated. The percentages are then used to create an alpha-channel mask (similar to the mask created above) through which the antialiased text may be rendered.
The above super sampling and vector extraction techniques assume that the background to which the text is applied is white/blank such that all that is needed in the rendering process is to apply the source color to the display device at a certain intensity level. However, such techniques are complicated when text is being placed on top of another image with multiple colors such as a scanned photograph. In such a situation, not only must the intensity level be applied to the source color, but that combined image must then be mixed with the background image (scanned photograph).
For example, after obtaining a mask value of 75%, and looking to the source image which provides information that the source color is blue, the 75% blue must then be mixed with the background image. If the text is being placed over an orange sunset, then the 75% blue pixel is mixed with a 25% orange value. The final mix value is then illuminated on the display device. Similarly, if a 75% blue text character is being placed over a green tree, then the 75% blue pixel is mixed with a 25% green value and the final mixed value is illuminated on the display device.
An example which does not use colored text but patterned text is illustrated in FIG. 7. A source image or the pattern of the text 702 is retained in a source data block. In FIG. 7, the source image is a pattern containing a black background with white patterned dots 702. The mask 704 which was created is saved in another data block. The mask 704 contains the text "Hello, World". The image which the text is being placed on is a map of the world 706, and is referred to as the "destination". When drawing a boundary pixel of the final image 708, various steps occur: (1) the source pattern is obtained; (2) the mask/intensity value is obtained; (3) the appropriate intensity level of the pattern is mixed with the background 706; (4) the final mixed value is illuminated on the screen. Essentially, the source pattern 702 is filtered through (or peeks through) the mask 704 onto the resulting displayed image 708. The text has been anti-aliased by the mask filtering process and does not appear to have "jaggy" edges in the resulting display 708. As stated above, using the prior art method to perform such anti-aliasing consumes memory and is slow in that it requires approximately one to two seconds to draw the full screen of the final anti-aliased text.
The prior art use of memory is illustrated in FIG. 8. The memory unit 802 stores all data information. If anti-aliasing of the text were not performed, such data information would include the source text/color map 804 and a background or destination image 808. However, when performing anti-aliasing using the prior art, such data information includes the source text/color map 804, the mask 806, and the background or destination 808. All of which are in uncompressed bitmap form. The storage of data in this format is memory intensive (consumes a great deal of memory). In the prior art, the mask 806 and source text/color map 804 are blended 810 and the blended source-mask is mixed with the background 812 immediately prior to rendering on the display device 810. Nonetheless, the color map and mask remained stored in an uncompressed bitmap form. As FIG. 8 illustrates, using the prior art method to perform anti-aliasing consumes memory.
In the modern trend of today's computer systems, applications have grown technologically and in complexity. CD-ROM (Compact Disc-Read Only Memory) technology and increased processor speeds have enabled video, photographs, sound, and other multimedia tools to be effectively utilized by computer users. Nonetheless, programs which use the multimedia tools (referred to as multimedia applications) to display text messages still suffer from aliasing as described above. Due to the slow rendering process in the prior art, rendering text messages in real time in multimedia applications has been inadequate. Multimedia applications typically need to redraw full screen images in less than 1/10 of a second. The prior art methods, even when optimized, take approximately 1-2 seconds to draw a full screen of anti-aliased text on a common computer. When scrolling such anti-aliased text vertically on a computer screen, each time the text is moved, it would take 1-2 seconds. Such a speed deficit is inadequate for the common multimedia computer uses. The present invention overcomes these disadvantages of the prior art.
U.S. Pat. No. 4,704,605, with a first listed inventor of Edelson, relates to a method and apparatus for providing anti-aliased edges in pixel-mapped computer graphics. The invention uses smoothing information consisting of a mixed value that indicates what percentage of the new color is to be displayed in a given pixel. The value of the percentage for the old color is derived by subtracting the indicated percentage from one hundred percent. The patent discloses three methods for encoding the mixed value for a pixel.
The background section of Edelson '605 describes an anti-aliasing scheme. In this scheme, encoding is used to define several mixed color values, typically 16 such color values, that are shadings between the available object colors and a given background color. With an eight-bit word allotted for each pixel, such a system can provide 15 object colors. Each of these colors would have 15 internally defined additional colors that are intermediate shades between the object colors and a background color. For instance, if the object is blue and the background was black, the display system will produce one of fifteen internally defined shades between blue and the given background color (black) required to simulate a pixel 15/16 covered with blue, down to 1/16 covered with blue.
Edelson '605 attempts to address one disadvantage of this prior art system: The fact that the anti-aliasing is only possible between the given object colors and one designated background color. If one object color crosses in front of another object color, the edge again appears jagged since no intermediate shades are defined for this combination of colors.
The first method of Edelson '605 allocates specific bits for color and mixed values. The second method encodes either mixing or color values in each pixel word. The subsequent pixel word is checked before deciding the proper treatment of a given pixel. The third method either encodes a color value or multiple mixed values in each pixel word. The mix information is then displayed as a set of sub-pixels.
U.S. Pat. No. 4,908,780, with a first listed inventor of Priem, is directed to anti-aliasing raster operations utilizing sub-pixel crossing information to control pixel shading. Anti-aliasing is performed by logically dividing each addressable frame buffer pixel into sixteen sub-pixels and generating a gray scale value for the displayed pixel that is a function of the number of sub-pixels crossed by a portion of a rendered image. The invented circuitry is part of the circuitry used for combining source and destination data which forms the displayed image: an anti-aliasing mask and filter, adder/subtractor logic, saturation logic and anti-aliasing logic.
In Priem '780, each addressable frame buffer pixel in the frame buffer memory is logically divided into a group of sixteen sub-pixels so that the entire screen appears to the CPU as if it had sixteen times more monochrome pixels than it actually has, and is four times larger in the X and Y directions than is actually present in the frame buffer. This is referred to in Priem '780 as "The High Resolution Monochrome Mode." The high resolution monochrome data supplied to the CPU is eventually written to the lower resolution pixel coordinate stored in the frame buffer memory. When performing the mapping between the sub-pixel coordinates addressed by the CPU and the pixel coordinates stored in memory, the sub-pixel data (that is, sixteen separate bits of information for each pixel on the video screen) is converted to an appropriated gray scale value so that the anti-aliased line has appropriately shaded pixels at the edges of the line.
U.S. Pat. No. 4,918,626, with a first listed inventor of Watkins describes a computer graphics priority system with anti-aliasing. Image data is composed from polygons to attain data for displays with the removal of hidden surfaces and smooth appearing edges. Defined polygons are tested for priority in a determined field of vision by scan conversion to specify individual picture elements or pixels. In general, the system of Watkins '626 is directed to a process or product for resolving priority between polygons contending for individual areas in a display. Priority is resolved by defining the edge where the planes of the two polygons intersect, then by applying a simple test of sign values after transforming the edge to the space of the display screen and determining the slope of such an edge.
U.S. Pat. No. 5,065,144, with a first listed inventor of Edelson is directed to an apparatus for expanding the number of shades a low-end graphics system may employ. The encoder of Edelson '144 converts explicitly represented pixel values from an image source into "mix-run" encoded representations thereof and stores them into the locations of a display memory. A display mechanism draws the resultant stored data from the display memory and interprets them in accordance with a mix-run encoding scheme originally disclosed in the Edelson '605 patent. As a consequence, the system of Edelson '144 is able to provide a wide range of color shades with only modest sized display and palette memories.
According to Edelson '144, a mix-run encoder converts the strictly pixel by pixel representation into a mix-run representation. To perform the conversion, the encoder searches through the source pixel words to find sequences that lend themselves to translation into a run of pixel words in the mix-run representation. In the mix-run representation, a run is characterized by a set of two values from which the various mixes and the run are to be computed. The mix-run representation contains a fraction from which the pixel value is to be computed by applying the fraction to two pixel values to be mixed. The mix-run representation typically represents the characteristic values in essentially a pixel by pixel manner as the two pixel words at the start of the run, and it may choose as the characteristic values those at the beginning and end of the source sequence that it translates into the run. The remaining, intervening pixel words in the run represent their pixel values as fractions, which must be applied to the two characteristic values for that run to arrive at the intended pixel values.
The encoder begins by inspecting a short sequence from the source pixel words that make-up an image. If the pixel values that the sequence represents can be adequately approximated as mixes of a common set of characteristic values, the encoder recognizes that sequence as one acceptable for translation, adds a further source pixel word to it, and determines whether the lengthened sequence is also acceptable. If so, the process continues. If not, it adopts the last acceptable sequence for translation into a run, and repeats the process with subsequent sequences.
U.S. Pat. No. 5,123,085, with a first listed inventor of Wells, is directed to a method and apparatus for rendering anti-aliased polygons so as to solve the hidden face problem. The pixels which comprise the edges and vertices of the polygon are first determined from the vertices which define the polygon. The alpha channel comprises either a sub pixel mask associated with each pixel which indicates the amount and sub pixel regions of coverage or a single value indicative of the percentage of coverage of a pixel. Furthermore, a z value indicative of the depth of each pixel is maintained. The pixels between the edge pixels of the polygon are then turned on, thereby filling the polygon. The pixels which comprise the polygon are then composited with the background pixels on a per pixel basis. The depth value of each pixel of the polygon (the z value) is used to determine the compositing equations to be used to composite each pixel of the polygon to the background.
U.S. Pat. No. 5,239,625, with a first listed inventor of Bogart, is directed to an apparatus and method for merging pages with high and low resolution items, such as photographic images coupled with text or graphics. An input image containing high resolution images and low resolution items are rasterized twice, once at a high resolution and once at a low resolution. The rasterized images are represented in compressed form using a run-code encoding technique.
During the low resolution rasterization, only the low resolution graphic elements are rasterized. At places in the image where there are no low resolution elements arbitrary data is substituted. This data is used as a place holder, but will otherwise be ignored. During the high resolution rasterization, only the high resolution graphic elements of the input image are rasterized. Data for the background is included so that the background will also be imaged. In places where their are low resolution image elements, a reserved intensity value is substituted.
The rasterized images are represented in compressed form using a run code encoding technique. In run-code encoding, continuous pixels along a single raster line having the same value are represented by one pixel and a repeat count pixel. Identical contiguous lines are represented by one line and a repeat line count.
U.S. Pat. No. 5,261,030, with a first listed inventor of Brooke describes a real time digital computer graphics processing method and apparatus for performing dynamic stairstepping anti-aliasing in systems employing dynamic images, such as visual simulation systems. Using Brooke '030, aliasing of digital computer images rendered in a simulation are reduced. Realtime pixel mixing is accomplished by processing each pixel of a digitally computer foreground image generated in real time with the corresponding pixel of a previously generated background image. The effect of the processing is to overlay the foreground image on the background image and cause the pixels on the periphery of each object rendered in the foreground image to be color blended with the corresponding pixels of the background image in such a manner as to soften the transition between the foreground and background images.
U.S. Pat. No. 5,295,235, with a first listed inventor of Newman, is directed to a polygon engine for rendering animation on a computer graphic display using a compressed data format. A display list of objects for the next frame is converted into a list of spans for each horizontal line of the display. The polygon engine converts the list spans for all objects into a set of run-length encoded bit map lines for the next frame. Conflicts between overlapping objects are resolved based on a depth value of the corresponding objects. Any remaining unspecified pixels are filled with a predetermined background color. The polygon engine updates the frame buffer to correspond to the set of run-length encoded bit map lines, preferably by comparing run-length encoded bit map lines for the next frame with those for the current frame, and writing only changed pixels into the frame buffer.
U.S. Pat. No. 5,303,334, with a first listed inventor of Snyder, is directed to an apparatus and method for rendering graphic images as bit maps. Following Snyder '334, the system consists of a single, relatively complex application specific integrated circuit (ASIC) connected high speed RAM. The primary function of the system is to render scanned or synthetic source images in black and white, gray, or color incorporating a fast, high quality screening method into the RIP's frame or banned buffer.
The system is used to improve raster imaging in many applications such as those which implement post script commands. Snyder '334 also describes the use of a mask in rendering text. The mask, which may be compressed (such as by using run-length encoding), is stored in uncompressed form in memory. The mask is then aligned bit by bit with the device buffer output as the character outline is scanned.
U.S. Pat. No. 5,369,739, with a first listed inventor of Akeley, is directed to an apparatus and method for generating point sample masks in a graphics display system. In Akeley '739, separate masks are generated for each edge of a polygon. These masks specify whether particular sub-sample points are within a half plane defined by an edge of the polygon. This is determined by examining the sign of vertical or horizontal distance metrics corresponding to those sample points. These separate masks are merged to form the final point sample mask. The final point sample mask contains information specifying whether particular sample points reside within the polygon.
U.S. Pat. No. 5,422,995, with a first listed inventor of Aoki, is directed to a method for decoding run-length encoded bit strings to increase the speed at which the bit strings may be written into bit mapped memory. The invention of Aoki '995 skips over a range of bit memory mapped addresses, reducing the number of write operations into the bit mapped memory.
U.S. Pat. No. 5,490,238, with a first listed inventor of Watkins describes an attribute blending system for composing computer graphic images from objects, such as polygons. Using Watkins '238, objects contending for pixel representation on a graphics display selectively are awarded a fractional area within a pixel on the basis of coarse calculations in the z dimension, aggregate demands of the objects, and blending techniques free of binary position resolutions. The area occupied by a polygon within a pixel is represented using a single number, which may variously be defined, for example, a value of 0 indicates no area is occupied within the pixel, while a value of 255 indicates full pixel coverage. Fine calculations in the z dimension for binary resolutions are avoided by blending techniques to provide anti-aliasing.
In general, the system of Watkins '238 involves a simplified processing technique for solving the hidden surface problem with anti-aliasing. The binary decision between pairs of contending polygons either is simplified or ignored. If the contending objects are widely spaced apart along the depth dimension, the pixel simply may be awarded to the nearest object. If the objects are relatively near, the individual demands on the pixel are determined. If the demands of objects can be accommodated within the capacity of the pixel, the resulting mixture is calculated. If the demands cannot be accommodated, the attributes of the objects are mixed or blended with consideration to the relative range of the objects.
U.S. Pat. No. 5,497,434, with a first listed inventor of Wilson, describes a method and apparatus for performing image data compression, such as in processing digital video images. The invention is directed to reducing the processing requirements for producing video images from a compressed data string. The decompression side of the system forms a sequence of arrays of pixel display values for driving a display device from a stream of compressed data containing compressed data codes. Each of the arrays of pixel display values represents a frame of a moving image. Pixel copy codes within the stream of compressed data trigger copying at one or more previously formed pixel display values to a current position within a sequence of positions within the array along which decompression progresses.